package com.guaoran.algorithm.binary.tree.order;

import com.guaoran.algorithm.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Auth gucheng
 * @Desc 二叉树前序遍历：根 - 左 - 右
 * https://leetcode.com/problems/binary-tree-preorder-traversal/submissions/
 * @Date 2021/1/19 上午11:44
 */
public class PreOrderTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode right = new TreeNode(2);
        right.left = new TreeNode(3);
        root.right = right;
        System.out.println(preOrderTraversalDemo(root));
        System.out.println(preOrderTraversal(root));

    }

    private static List<Integer> preOrderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }

        return result;
    }

    /**
     * 递归方式
     * @param root
     * @return
     */
    public static List<Integer> preOrderTraversalDemo(TreeNode root) {
        List<Integer> result = new ArrayList();
        if(root == null){
            return result;
        }

        List<Integer> left = preOrderTraversalDemo(root.left);
        List<Integer> right = preOrderTraversalDemo(root.right);
        result.add(root.val);
        result.addAll(left);
        result.addAll(right);
        return result;
    }
}
